package main

import (
	"fmt"
	"log"
)

// Data 数据结构体
type Data struct {
	Id         int
	Tag        string
	TagContent string
	Level      int
	Y          int
	Attr       string
	//x     int
}

// EdgeNode 图边结构体
type EdgeNode struct {
	index int       // 顶点的图数组中的索引值
	next  *EdgeNode // 边连接的下一个顶点信息，边是两个顶点之间的连接
}

// VerNode 图顶点结构体
type VerNode struct {
	//data  int // 顶点存储的数据，如果是很多数据，这里可以指向一个结构体的指针
	data  *Data
	edges *EdgeNode // 结点的边
}

// Graph 图的结构体
type Graph struct {
	VerNodes []VerNode // 顶点集合
	EdgeCnt  int       // 边结构的总数
	VerCnt   int       // 顶点结构总数
}

type DataOption interface { // 结构体接口
	apply(*Data)
}

// 结构体接口功能选项
type funcOption struct {
	f func(*Data)
}

// 应用方法，需要传入数据结构体的参数用于应用结构体接口功能选项的f方法
func (fdo *funcOption) apply(do *Data) {
	fdo.f(do)
}

// 工厂模式 相当于构造函数
func newFuncOption(f func(*Data)) *funcOption {
	return &funcOption{
		f: f,
	}
}

// 通过类构造函数的方法传值
func setTag(s string) DataOption {
	return newFuncOption(func(o *Data) {
		o.Tag = s
	})
}

func setTagContent(s string) DataOption {
	return newFuncOption(func(o *Data) {
		o.TagContent = s
	})
}

func setTable(s int) DataOption {
	return newFuncOption(func(o *Data) {
		o.Level = s
	})
}

func setAttr(s string) DataOption {
	return newFuncOption(func(o *Data) {
		o.Attr = s
	})
}

//默认参数
func defaultOptions() Data {
	return Data{
		Tag:        "",
		TagContent: "",
		Attr:       "",
	}
}

// 连接结构体
type clientConn struct {
	data Data
}

// CreateTagLeft 返回左标签改良方法
func CreateTagLeft(opts ...DataOption) string { // 接收任意个结构体接口
	cc := &clientConn{
		data: defaultOptions(),
	}
	//循环调用opts
	for _, opt := range opts {
		opt.apply(&cc.data)
	}
	//fmt.Printf("%+v\n",cc.dopts)
	//fmt.Println(cc.data)
	tagLeft := ""
	if cc.data.Tag != "{}" {
		if cc.data.Attr == "" {
			tagLeft = `<` + cc.data.Tag + `>`
		} else {
			tagLeft = `<` + cc.data.Tag + ` ` + cc.data.Attr + `>`
		}
	} else {
		tagLeft = "{ \n" + MakeTagCount(cc.data.Level+1)
	}

	return tagLeft
}

// CreateTagRight 返回右标签改良方法
func CreateTagRight(opts ...DataOption) string { // 接收任意个结构体接口
	cc := &clientConn{
		data: defaultOptions(),
	}
	//循环调用opts
	for _, opt := range opts {
		opt.apply(&cc.data)
	}
	tagRight := ""
	if cc.data.Tag != "{}" {
		if cc.data.Tag == "input" {
			tagRight = ""
		} else {
			tagRight = `</` + cc.data.Tag + `>`
		}
	} else {
		tagRight = cc.data.TagContent + "\n" + MakeTagCount(cc.data.Level+1) + "}"
	}

	return tagRight
}

// 定位顶点的索引位置
func (g *Graph) findIndex(verValue int) int {
	for i := 0; i < g.VerCnt; i++ {
		if g.VerNodes[i].data.Id == verValue {
			return i
		}
	}
	return -1
}

func (g *Graph) AddEdge(verValue1 int, verValue2 int) {
	// 先定位,根据顶点返回来的i作为具体边的index值
	index1, index2 := g.findIndex(verValue1), g.findIndex(verValue2)
	if index1 == -1 || index2 == -1 {
		log.Fatalln("非法顶点值")
	}

	// 准备好边节点
	edgeNode1 := &EdgeNode{index: index1}
	edgeNode2 := &EdgeNode{index: index2}

	// 头插法，这样不用遍历节点链表，节省时间
	edgeNode2.next = g.VerNodes[index1].edges
	g.VerNodes[index1].edges = edgeNode2

	edgeNode1.next = g.VerNodes[index2].edges
	g.VerNodes[index2].edges = edgeNode1
	g.EdgeCnt += 1
}

// 普通遍历

func (g *Graph) Show() {
	for i := 0; i < g.VerCnt; i++ {
		head := g.VerNodes[i].edges
		print("普通遍历：")
		print(g.VerNodes[i].data.Tag)
		for head != nil {
			print("->")
			print(g.VerNodes[head.index].data.Tag)
			head = head.next
		}
		print("\n")
	}
}

/*func (vn VerNode) String() string {
	return fmt.Sprintf("VerNode{data: %d, edges: %p}", vn.data, vn.edges)
}*/
// 广度优先遍历 BFS
//func (g *Graph) BFSShow(node *VerNode) {
//	// 用以记录已遍历的节点索引
//	visited := make(map[*VerNode]struct{})
//	queue := make([]*VerNode, 0)
//	queue = append(queue, node)
//	for len(queue) != 0 {
//		// 模拟出队列，从头取出一个，然后队列就少了一个元素
//		currNode := queue[0]
//		queue = queue[1:]
//		// 如果已遍历，则继续循环
//		if _, ok := visited[currNode]; ok {
//			continue
//		}
//		log.Println(currNode.data)
//		//if currNode.edges.next != nil{
//		//}
//		visited[currNode] = struct{}{}
//		head := currNode.edges
//		for head != nil {
//			queue = append(queue, &g.VerNodes[head.index])
//			head = head.next
//		}
//	}
//}
// 深度优先遍历 DFS
//func (g *Graph) DFSShow(node *VerNode) {
//	var max int
//	// 也需要一个变量暂时保存是否访问过
//	visited := make(map[*VerNode]struct{})
//	// 用数组实现一个简单栈，先压入栈中
//	stack := make([]*VerNode, 0)
//	//stackEnd := make([]string, 0)
//	stack = append(stack, node)
//	strs := ""
//	for len(stack) != 0 {
//		maxIndex := len(stack) - 1
//		if max < maxIndex {
//			max = maxIndex
//		}
//		// 先进后出，模拟出栈，取栈中的最后一个数据
//		currNode := stack[maxIndex]
//		/*if max == currNode.data.Level-1 {
//			t = stack[len(stack)-1].data.Tag
//		}*/
//		stack = stack[:maxIndex]
//		le := len(stack)
//		if _, ok := visited[currNode]; ok { // 是否空 ，空
//			// 标记最后最大层级
//			var maxLevel int
//			for _, v := range stack {
//				if maxLevel < v.data.Level {
//					maxLevel = v.data.Level
//				}
//			}
//			// 添加最后的闭合标签
//			if le == 0 && len(stack) == 0 {
//				strs += MakeTagRight(currNode.data.Tag)
//			}
//			// 添加各级闭合标签
//			if currNode.data.Level >= maxLevel && currNode.edges.next != nil && len(stack) != 0 {
//				strs += MakeTagRight(currNode.data.Tag)
//			}
//			continue
//		}
//		//log.Println(currNode.edges.next)
//		strs += MakeTagLeft(currNode.data.Tag)
//		if currNode.edges.next == nil {
//			strs += MakeTagRight(currNode.data.Tag)
//		}
//		visited[currNode] = struct{}{}
//		head := currNode.edges
//		//fmt.Println(head.index,head.next)
//		for head != nil { // 有子节点，将子节点压进栈
//			stack = append(stack, &g.VerNodes[head.index])
//			head = head.next
//		}
//	}
//	println(strs)
//}
/*// MakeTagLeft 格式化标签对1：左标签
func MakeTagLeft(tagName string, Style string) string {
	tagLeft := ""
	if Style == "" {
		tagLeft = `<` + tagName + Style + `>`
	} else {
		tagLeft = `<` + tagName + ` style="` + Style + `"` + `>`
	}
	return tagLeft
}*/
/*// MakeTagRight 格式化标签对2：右标签
func MakeTagRight(tagName string) string {
	tagRight := ""
	if tagName == "{}" {
		tagRight = `}`
	} else {
		tagRight = `<` + tagName + `>`
	}
	return tagRight

}*/

// MakeTagCount 按数量生成制表符
func MakeTagCount(nodeLength int) string {
	var tabCount = ""
	for i := 0; i < nodeLength-1; i++ {
		tabCount += "\t"
	}
	return tabCount
}

// BubbleSort 冒泡排序
func BubbleSort(arr []*VerNode) []*VerNode {
	// 循环体
	for i := 0; i < len(arr)-1; i++ {
		for j := 0; j < len(arr)-1-i; j++ { //-i是为了节省内存
			if (arr)[j].data.Y > (arr)[j+1].data.Y {
				(arr)[j], (arr)[j+1] = (arr)[j+1], (arr)[j] // 交换
			}
		}
	}
	return arr
}

// DFSRecur 模拟栈调用输出
func (g *Graph) DFSRecur(node *VerNode) string {
	// 也需要一个变量暂时保存是否访问过
	visited := make(map[*VerNode]struct{})
	// 用数组实现一个简单栈，先压入栈中
	stack := make([]*VerNode, 0)
	stack = append(stack, node) // 将顶点压入栈中
	// 新建一个数组，用于存放标签，每生成一个就压进去一个，新建一个公有的变量，
	// 判断每次标签的level和上一次的比较，如果大的，就放前标签，后标签先不放，如果小的就从数组取出最后一次压进去的标签，
	// 再接上新标签，如果是连续小的话就以此类推
	str := ""                       // 累加字符串
	lev := 0                        // 记录前一个层级大小，进行层级比较
	tagStack := make([]*VerNode, 0) // 右标签栈，模拟先进后出
	// 模拟栈深度搜索，深度搜索，按顺序输出
	for len(stack) != 0 {
		maxIndex := len(stack) - 1
		// 先进后出，模拟出栈，取栈中的最后一个数据
		currNode := stack[maxIndex]
		stack = stack[:maxIndex]
		// 检索当前节点是否已经输出过，若已经输出过，则判断是否进入最后节点，否则跳出输出当前节点
		if _, okk := visited[currNode]; okk {
			// 如果当前节点已经输出过，而且栈中已经没有节点了，表示遍历完成，将右标签栈全部遍历出来
			if len(stack) == 0 {
				for len(tagStack) != 0 {
					maxtags := len(tagStack) - 1
					if tagStack[maxtags].data.Level == lev { //当level相同的时候，表示在同一级闭合标签，无需制表符
						str += CreateTagRight(setTag(tagStack[maxtags].data.Tag), setTagContent(tagStack[maxtags].data.TagContent), setTable(currNode.data.Level)) + "\n" // 生成后标签 CreateTagRight(setTag(tagStack[maxtags].data.Tag))\MakeTagRight(tagStack[maxtags].data.Tag)
					} else if tagStack[maxtags].data.Level < lev && tagStack[maxtags].data.Level != 1 {
						// 当level小于趋势lev时，且不等于1时，说明开始闭合父级标签，根据level数量生成对应制表符
						str += MakeTagCount(tagStack[maxtags].data.Level) + CreateTagRight(setTag(tagStack[maxtags].data.Tag), setTagContent(tagStack[maxtags].data.TagContent), setTable(currNode.data.Level)) + "\n" // 生成后标签
					} else { //上述条件不成立，说明level等于1，代表需要闭合顶点标签
						str += CreateTagRight(setTag(tagStack[maxtags].data.Tag), setTagContent(tagStack[maxtags].data.TagContent), setTable(currNode.data.Level)) + "\n" // 生成后标签
					}
					tagStack = tagStack[:maxtags]
				}
			}
			continue
		}
		// 以下是判断层级关系，进行取栈与压栈操作
		if lev < currNode.data.Level { // 当前层级比前一个层级高，表示在进行嵌套关系，输出左标签，将右标签压入栈中
			lev = currNode.data.Level
			tagStack = append(tagStack, currNode)
			str += "\n" + MakeTagCount(lev) + CreateTagLeft(setTag(currNode.data.Tag), setAttr(currNode.data.Attr), setTable(currNode.data.Level)) //MakeTagLeft(currNode.data.Tag, currNode.data.Style)
		} else if lev == currNode.data.Level { // 当前层级等于前一个层级，表示层级平行，将右标签输出后，输出左标签
			maxtags := len(tagStack) - 1
			str += CreateTagRight(setTag(tagStack[maxtags].data.Tag), setTagContent(tagStack[maxtags].data.TagContent), setTable(currNode.data.Level)) // 生成后标签
			tagStack = tagStack[:maxtags]
			// 输出左标签
			lev = currNode.data.Level
			tagStack = append(tagStack, currNode)
			str += "\n" + MakeTagCount(lev) + CreateTagLeft(setTag(currNode.data.Tag), setAttr(currNode.data.Attr), setTable(currNode.data.Level))
		} else { // 当前层级比前一个层级低，表示退出嵌套关系，需要将所有右边全部闭合，再输出左标签，进入下一层的关系
			maxtags := len(tagStack) - 1
			str += CreateTagRight(setTag(tagStack[maxtags].data.Tag), setTagContent(tagStack[maxtags].data.TagContent), setTable(currNode.data.Level)) + "\n" // 生成后标签
			tagStack = tagStack[:maxtags]
			// 上下这两段其实可以合并，但若合并，格式化效果有无，上段为了退出当前层级，换行处理，
			// 下段需要加制表符，为了将标签栈中的未闭合的所有标签闭合
			for {
				maxtags := len(tagStack) - 1
				str += MakeTagCount(tagStack[maxtags-1].data.Level+1) + CreateTagRight(setTag(tagStack[maxtags].data.Tag), setTagContent(tagStack[maxtags].data.TagContent), setTable(currNode.data.Level)) + "\n" // 生成后标签
				tagStack = tagStack[:maxtags]
				if tagStack[maxtags-1].data.Level < currNode.data.Level {
					// 当右标签栈中的最后一个层级比当前的节点层级要小，退出右标签闭合，进入当前左标签生成
					break
				}
			}
			// 进入当前左标签生成
			lev = currNode.data.Level
			tagStack = append(tagStack, currNode)
			str += MakeTagCount(lev) + CreateTagLeft(setTag(currNode.data.Tag), setAttr(currNode.data.Attr), setTable(currNode.data.Level))
		}
		//log.Println(currNode.data)
		visited[currNode] = struct{}{} // 记录当前节点
		head := currNode.edges         // 当前节点第一个子节点
		//nowNode := currNode
		// 为了查找当前节点所有子节点的初始变量，用于控制深度搜索分支
		next1 := currNode.edges
		var vnArr []*VerNode                                // 初始一个图关系节点切片，用于存储所有查找到的子节点，引用类型
		var visitSortEnd []*VerNode                         // 初始一个图关系节点切片，用于存排序后的节点，引用类型
		if _, ok := visited[&g.VerNodes[head.index]]; !ok { // 如果当前子节点未添加过的
			vnArr = append(vnArr, &g.VerNodes[next1.index]) // 将当前节点压进切片中
			for {                                           // 获取所有边的index，用于查找vn
				next1 = next1.next // 拿到节点中的下一子节点，重复替换，直至当前子节点为nil，退出
				if _, ok := visited[&g.VerNodes[next1.index]]; ok {
					// 记录是否为已输出过的节点，是则不加入到数组中，另外存放，在后面加到排序好后的数组第一位
					//repeatVn = g.VerNodes[next1.index]
					visitSortEnd = append(visitSortEnd, &g.VerNodes[next1.index])
					break
				}
				vnArr = append(vnArr, &g.VerNodes[next1.index]) // 将查找到的节点压入数组
				if next1.next == nil {                          // 退出条件
					break
				}
			}
		} else {
			//repeatVn = g.VerNodes[next1.index]
			// 当前节点添加过时，直接存入当前添加过的节点到visitSortEnd中
			visitSortEnd = append(visitSortEnd, &g.VerNodes[next1.index])
		}
		//if _, ok := visited[&g.VerNodes[next1.index]]; ok {	}
		//var sortEnd []VerNode
		sortEnd := BubbleSort(vnArr) //获取排序后的切片/栈
		for head != nil {
			// 判断当前节点是否已经添加过，则将排序后的切片压入visitSortEnd，栈形式取出最后一个压入stack中（一般出现在最后一次）
			// 模拟按默认顺序取出子节点，按每次压入一个的形式，对压入stack的子节点做相应的排序，y大的先入(后出)
			if _, ok := visited[&g.VerNodes[head.index]]; ok {
				visitSortEnd = append(visitSortEnd, sortEnd...)
				maxSortEnd := len(visitSortEnd) - 1
				// 先进后出，模拟出栈，取栈中的最后一个数据 压栈 取代按默认顺序取出子节点
				stack = append(stack, visitSortEnd[maxSortEnd])
				sortEnd = visitSortEnd[:maxSortEnd] // 将栈中最后一个切除
			} else { // 当前节点未添加过，则将排序后的切片每次最后一个压入stack
				maxSortEnd := len(sortEnd) - 1
				// 先进后出，模拟出栈，取栈中的最后一个数据 压栈
				stack = append(stack, sortEnd[maxSortEnd])
				// 将栈中最后一个切除
				sortEnd = sortEnd[:maxSortEnd]
			}
			//stack = append(stack, &g.VerNodes[head.index])
			// 覆盖当前节点，进行下一个相邻节点
			head = head.next
		}
	}
	return str
}

func NewGraph(vCnt int) *Graph {
	vNodes := make([]VerNode, 0, vCnt)
	/*vNodes = append(vNodes, VerNode{data: &Data{Id: 1, Tag: "div", Level: 1, Y: 1}}) // 顶点
	vNodes = append(vNodes, VerNode{data: &Data{Id: 2, Tag: "form", Level: 2, Y: 5}})
	vNodes = append(vNodes, VerNode{data: &Data{Id: 3, Tag: "button", Level: 2, Y: 6}})
	vNodes = append(vNodes, VerNode{data: &Data{Id: 4, Tag: "Cmp_Logo", Level: 2, Y: 1}})
	vNodes = append(vNodes, VerNode{data: &Data{Id: 5, Tag: "input1", Level: 3, Y: 2}})
	vNodes = append(vNodes, VerNode{data: &Data{Id: 6, Tag: "input2", Level: 3, Y: 1}})*/

	// 注意，添加节点需要标记清除层级，否则会出现嵌套错误，增加y属性，y值大的排在后面
	vNodes = append(vNodes, VerNode{data: &Data{Id: 1, Tag: "div", Level: 1, Y: 1, Attr: `style="width: 100px;"`}}) // 顶点
	vNodes = append(vNodes, VerNode{data: &Data{Id: 2, Tag: "form", Level: 2, Y: 2, Attr: `id="testFrom" class="test" action="get"`}})
	vNodes = append(vNodes, VerNode{data: &Data{Id: 3, Tag: "button", Level: 2, Y: 3}})
	vNodes = append(vNodes, VerNode{data: &Data{Id: 4, Tag: "Cmp_Logo", Level: 2, Y: 1}})
	vNodes = append(vNodes, VerNode{data: &Data{Id: 5, Tag: "input", Level: 5, Y: 2}})
	vNodes = append(vNodes, VerNode{data: &Data{Id: 6, Tag: "input", Level: 4, Y: 1}})
	vNodes = append(vNodes, VerNode{data: &Data{Id: 7, Tag: "div1", Level: 3, Y: 4, Attr: `style="width: 100px;"`}})
	vNodes = append(vNodes, VerNode{data: &Data{Id: 8, Tag: "div2", Level: 3, Y: 3}})
	vNodes = append(vNodes, VerNode{data: &Data{Id: 9, Tag: "div3", Level: 4, Y: 1}})
	vNodes = append(vNodes, VerNode{data: &Data{Id: 10, Tag: "{}", Level: 3, Y: 1, TagContent: `func(){test()}`}})

	/* vNodes = append(vNodes, VerNode{data: &Data{Id: 8, Tag: "text", Level: 3}})
	for i := 1; i <= vCnt; i++ {
		vNodes = append(vNodes, VerNode{data: &Data{Id: i, Tag: "div" }})
	}*/
	return &Graph{
		EdgeCnt:  0,
		VerCnt:   vCnt,
		VerNodes: vNodes,
	}
}
func main() {
	vCnt := 10
	graph := NewGraph(vCnt)
	// 模拟上图的图连接，增加节点之间的边
	/*graph.AddEdge(1, 2)
	graph.AddEdge(1, 3)
	graph.AddEdge(1, 4)
	graph.AddEdge(2, 5)
	//graph.AddEdge(5, 8)
	graph.AddEdge(2, 6)*/
	//graph.AddEdge(5, 8)
	graph.AddEdge(1, 2)
	graph.AddEdge(1, 3)
	graph.AddEdge(1, 4)
	graph.AddEdge(4, 10)
	graph.AddEdge(2, 7)
	graph.AddEdge(7, 9)
	graph.AddEdge(9, 5)
	graph.AddEdge(2, 8)
	graph.AddEdge(8, 6)

	//graph.AddEdge(8, 6)
	//graph.Show()
	log.Println("DFS---------")
	var str = graph.DFSRecur(&graph.VerNodes[0]) //确认顶点位置
	fmt.Println(str)
}
